#include "RabinKarp.h"

//===========================================================================
//
// Constructor
//
//		Parameters: sigs - reference to a _signatures vector
//
RabinKarp::RabinKarp()
:_modu(MODULU),_primeBase(PRIME),_shortestSigLength(SHORTEST_LENGTH)
{
	init();
}
//===========================================================================
//
//  Destructor
//
RabinKarp::~RabinKarp(void)
{
}

//===========================================================================
//
// init(): Calculate the hash values of each signature
//
void RabinKarp::init()
{
	vector<string>::iterator itr;
	for(itr = _signatures.begin(); itr != _signatures.end(); itr++)
	{
		_hashSignatures.push_back(hashVal(*itr));
		_signaturessLengths.push_back((*itr).length());

		if(  _shortestSigLength > (int)((*itr).length())  )
		{
			_shortestSigLength=(*itr).length();
		}
	}
	_numSignatures=_signatures.size();
}
//===========================================================================
//
// power()
//
//
unsigned long RabinKarp::power(int base,int exp)
{
	unsigned long num=1;
	switch(exp)
	{
		case 0:
			return 1;
		case 1:
			return base;
		case 2:
			return (base*base);
		default:
			for(int i=0;i<exp;i++)
			{
				num=num*base;
			}
	}
	return num;
}
//===========================================================================
//
// hashVal() - calculates the hash value of a string
//
//			Parameters: s - reference to a string
//
//			Return value: the hash value of a string
//
int RabinKarp::hashVal(string &s)
{
	int maxindex=s.length()-1;
	int hash=0;
	int j=0;
	int i=0;
	int pow=0;

	for(i=maxindex;i>=0;i--)
	{
		pow=power(_primeBase,i);
		hash=hash+int(s[j++])*pow;
	}
	return hash%_modu;
}



//===========================================================================
//
// findSignatures() - searches for signatures in a string
//
//			Parameters: data - reference to a string to search
//
//			Retrun value: the index of the signature (if found) in the _signatures vector, otherwise -1
//
int RabinKarp::findSignatures(const string &data)
{
	int i=0;
	int j=0;
	int index=0;
	int firstChar=0;
	vector<int>::iterator itr;
	int maxIndexToSearch=data.length()-_shortestSigLength;
	string sub="";
	unsigned long substrHash=0;

	for(itr = _signaturessLengths.begin(); itr != _signaturessLengths.end(); itr++)
	{
		try
		{
			sub=data.substr(0,(*itr));
			substrHash=hashVal(sub);
		}
		catch(...)
		{
			cout<<"Problem in sub=data.substr(0,(*itr));"<<endl;
			return NOT_FOUND;
		}

		for(i=1;i<maxIndexToSearch;i++)
		{
			firstChar=sub[0];
			//check if substrHash matches any hash in vector<int>_hashSignatures
			for(j=0;j<(int)_signatures.size();j++)
			{
				if( substrHash==(_hashSignatures[j]) )
				{
					if( (sub.compare(_signatures[j]))==0 )
					{
						return j;
					}
				}
			}//for(j=0
			try
			{
				//sub is new substring --> one right shift
				sub=data.substr(i,*itr);
			}
			catch(...)
			{
				cout<<"Problem in sub=data.substr(0,(*itr));  2 "<<endl;
				return NOT_FOUND;
			}
			//recalculate hash value of sub
			substrHash-=(firstChar*power(_primeBase,sub.length()-1));
			substrHash*=_primeBase;
			substrHash+=(int)(sub[sub.length()-1]);
			substrHash%=_modu;

		}//for(i=0

	}//for(itr =

	return NOT_FOUND; // signature not found !!!
}

